public class MyLinkedList {
    //头指针
    ListNode head;

    //链表长度
    int size;

    //尾指针
    ListNode last;


    //利用静态内部类定义结点
    static class ListNode {
        int data;
        ListNode next;
        ListNode prev;

        public ListNode(int data) {
            this.data = data;
        }
    }

    //头插法
    public void addFirst(int data) {

        ListNode newNode = new ListNode(data);
        if(head == null && last == null) {
            head = newNode;
            last = newNode;
            this.size++;
        }else {
            newNode.prev = head.prev;
            newNode.next = head;
            head.prev = newNode;
            head = newNode;
            newNode.prev = null;
            this.size++;
        }
    }
    //尾插法
    public void addLast(int data) {
        if(head == null) {
            addFirst(data);
        }
        else {
            ListNode newNode = new ListNode(data);
            newNode.next = last.next;
            newNode.prev = last;
            last.next = newNode;
            last = newNode;
            this.size++;
        }
    }
    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex(int index,int data){
        //检查index是否合法
        if(index < 0 || index > size) {
            return false;
        }

        //下标为0则执行头插法
        if(index == 0) {
            addFirst(data);
            return true;
        }

        //执行尾插法
        if(index == size) {
            addLast(data);
            return true;
        }

        //寻找想要插入元素位置
        ListNode cur = this.head;
        int count = 0;
        while(count < index) {
            cur = cur.next;
            count++;
        }

        //构造新的结点
        ListNode newNode = new ListNode(data);
        //执行前插逻辑
        newNode.prev = cur.prev;
        newNode.next = cur;
        cur.prev.next = newNode;
        cur.prev = newNode;
        this.size++;
        return true;
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key) {
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.data == key) {
                return true;
            }

            cur = cur.next;
        }
        return false;
    }
    //删除第一次出现关键字为key的节点
    public void remove(int key) {
        //判空
        if(this.size == 0) {
            return;
        }

        if(!contains(key)) {
            return;
        }

        //头部结点和尾部结点需要特殊的处理
        ListNode cur = this.head;
        while(cur != null) {
            if(cur.data == key) {
                break;
            }
            cur = cur.next;
        }

       if(cur == this.head) {
           //如果删除的结点是第一个结点
           this.head = this.head.next;
           this.size--;
           return;
       }

       if(cur == this.last) {
           //如果删除的是最后一个结点
           this.last.prev.next = this.last.next;
           this.last = this.last.prev;
           this.size--;
           return;
       }

       //正常处理即可
       cur.prev.next = cur.next;
       cur.next.prev = cur.prev;
       this.size--;
    }
    //删除所有值为key的节点
    public void removeAllKey(int key) {
         //利用快慢双指针法，先处理尾部的结点
        //链表为空则直接退出
        if(this.head == null) {
            return;
        }

        ListNode fast = this.head.next;
        ListNode slow = this.head;

        while(fast != null) {
            if(fast.data == key) {
                //判断fast是否为最后一个结点
                if(fast.next == null) {
                    slow.next = fast.next;
                    fast = fast.next;
                    this.size--;
                }
                else{
                    slow.next = fast.next;
                    fast.next.prev = slow;
                    fast = fast.next;
                    this.size--;
                }
            }else {
                fast = fast.next;
                slow = slow.next;
            }
        }

        //处理头部节点
        assert this.head != null;
        if(this.head.data == key) {
            //判断链表是不是只有一个结点
            if(this.head.next == null) {
                this.head = this.head.next;
            }else {
                this.head.next.prev = this.head.prev;
                this.head = this.head.next;
            }
            this.size--;
        }
    }
    //得到单链表的长度
    public int size() {
        return this.size;
    }
    public void display() {
        if(head == null) {
            System.out.println("链表为空");
        }

        ListNode cur = head;
        while(cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }

        System.out.println();
    }
    public void clear() {
          //从头到尾进行断链，然后再将头尾指针置为null，最后将计数器size的值变为0
         ListNode cur = this.head;
         ListNode curN;
         while(cur != null) {
             curN = cur.next;
             //执行断链操作
             cur.prev = null;
             cur.next = null;

             cur = curN;
         }

         //将头指针和尾指针全部置为空
         this.head = null;
         this.last = null;
         //维护size计数器
         this.size = 0;
    }

    public static void main(String[] args) {
        MyLinkedList myLinkedList = new MyLinkedList();
        myLinkedList.display();
        myLinkedList.addLast(12);
        myLinkedList.display();
        myLinkedList.remove(12);
        myLinkedList.display();
    }
}
